/*
 * @lc app=leetcode.cn id=212 lang=cpp
 *
 * [212] 单词搜索 II
 */
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <unordered_set>

using namespace std;
// @lc code=start
class Solution {
public:
    unordered_set<string> to_find,found;
    vector<vector<int>> direct = {{1,0},{-1,0},{0,1},{0,-1}};
    vector<string> ret;
    int m,n;
    int max_length = 0;
    string tmp;
    void dfs(int path_i,int path_j,vector<vector<char>>& board,vector<vector<int>>& visited) {
        if(tmp.length() > max_length) {
            return ;
        }
        if(to_find.count(tmp)) {
            found.insert(tmp);
        }
        for(int i = 0;i < direct.size();i++) {
            int new_i = path_i + direct[i][0];
            int new_j = path_j + direct[i][1];
            if(new_i >= 0 && new_i < m && new_j >= 0 && new_j < n && !visited[new_i][new_j]) {
                visited[new_i][new_j] = 1;
                tmp.push_back(board[new_i][new_j]);
                dfs(new_i,new_j,board,visited);
                tmp.pop_back();
                visited[new_i][new_j] = 0;
            }
        }
    }
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        m = board.size();
        n = board[0].size();
        vector<vector<int>> visited(m,vector<int>(n));
        for(string s: words) {
            max_length = max(max_length,int(s.length()));
            to_find.insert(s);
        }
        for(int i = 0;i < m;i++) {
            for(int j = 0;j < n;j++) {
                visited[i][j] = 1;
                tmp.push_back(board[i][j]);
                dfs(i,j,board,visited);
                tmp.pop_back();
                visited[i][j] = 0;
            }
        }
        for(string s:found) {
            ret.push_back(s);
        }
        return ret;
    }
};
// @lc code=end

